{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Apply Operations on Array to Maximize Sum of Squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对数组执行操作使平方和最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个 <strong>正</strong>&nbsp;整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以对数组执行以下操作 <strong>任意次</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个互不相同的下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，<strong>同时</strong>&nbsp;将&nbsp;<code>nums[i]</code>&nbsp;更新为&nbsp;<code>(nums[i] AND nums[j])</code> 且将&nbsp;<code>nums[j]</code>&nbsp;更新为&nbsp;<code>(nums[i] OR nums[j])</code>&nbsp;，<code>OR</code>&nbsp;表示按位 <strong>或</strong>&nbsp;运算，<code>AND</code>&nbsp;表示按位 <strong>与</strong>&nbsp;运算。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要从最终的数组里选择&nbsp;<code>k</code>&nbsp;个元素，并计算它们的 <strong>平方</strong>&nbsp;之和。</p>\n",
    "\n",
    "<p>请你返回你可以得到的 <strong>最大</strong>&nbsp;平方和。</p>\n",
    "\n",
    "<p>由于答案可能会很大，将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,6,5,8], k = 2\n",
    "<b>输出：</b>261\n",
    "<b>解释：</b>我们可以对数组执行以下操作：\n",
    "- 选择 i = 0 和 j = 3 ，同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ，结果数组为 nums = [0,6,5,10] 。\n",
    "- 选择 i = 2 和 j = 3 ，同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ，结果数组为 nums = [0,6,0,15] 。\n",
    "从最终数组里选择元素 15 和 6 ，平方和为 15<sup>2</sup> + 6<sup>2</sup> = 261 。\n",
    "261 是可以得到的最大结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,5,4,7], k = 3\n",
    "<b>输出：</b>90\n",
    "<b>解释：</b>不需要执行任何操作。\n",
    "选择元素 7 ，5 和 4 ，平方和为 7<sup>2</sup> + 5<sup>2</sup> + 4<sup>2</sup> = 90 。\n",
    "90 是可以得到的最大结果。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [apply-operations-on-array-to-maximize-sum-of-squares](https://leetcode.cn/problems/apply-operations-on-array-to-maximize-sum-of-squares/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [apply-operations-on-array-to-maximize-sum-of-squares](https://leetcode.cn/problems/apply-operations-on-array-to-maximize-sum-of-squares/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,6,5,8]\\n2', '[4,5,4,7]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        M = 10 ** 9 + 7\n",
    "        \n",
    "        bits = [0] * 30\n",
    "        for num in nums:\n",
    "            for i in range(30):\n",
    "                if num & (1 << i): bits[i] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            cur = 0\n",
    "            for i in reversed(range(30)):\n",
    "                if bits[i]:\n",
    "                    bits[i] -= 1\n",
    "                    cur += 1 << i\n",
    "            ans = (ans + pow(cur, 2, M)) % M\n",
    "                    \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        # 其实就是把别的数的1偷过来用\n",
    "        nums.sort(reverse=True)\n",
    "        cnt = [0] * 30\n",
    "        while nums:\n",
    "            x = nums.pop()\n",
    "            for d in range(30):\n",
    "                if x >> d & 1:\n",
    "                    cnt[d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        mod = 10 ** 9  + 7\n",
    "        while k:\n",
    "            k -= 1\n",
    "            x = 0\n",
    "            for d in range(29, -1, -1):\n",
    "                if cnt[d]:\n",
    "                    x |= 1 << d\n",
    "                    cnt[d] -= 1\n",
    "            ans = (ans + x ** 2) % mod\n",
    "        \n",
    "        return ans % mod\n",
    "                    \n",
    "    \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        M = max(nums)\n",
    "        d = []\n",
    "        i = 0\n",
    "        while 2 ** i <= M:\n",
    "            count = 0\n",
    "            for j in range(len(nums)):\n",
    "                if nums[j] % 2 == 1:\n",
    "                    count += 1\n",
    "                nums[j] = nums[j] // 2\n",
    "            d.append(count)\n",
    "            i += 1\n",
    "        \n",
    "        d = [min(x, k) for x in d]\n",
    "        ans = 0\n",
    "        n = len(d)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if j == i:\n",
    "                    ans += d[i] * 2 ** (2 * i)\n",
    "                else:\n",
    "                    ans += min(d[i], d[j]) * 2 ** (i + j + 1)\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        MOD = int(10**9+7)\n",
    "        n = len(nums)\n",
    "        dp = []\n",
    "        while True:\n",
    "            has = False\n",
    "            cur = 0\n",
    "            for i in range(n):\n",
    "                if nums[i] != 0:\n",
    "                    has = True\n",
    "                if nums[i] % 2 == 1:\n",
    "                    cur += 1\n",
    "                nums[i] //= 2    \n",
    "            if has:\n",
    "                dp.append(cur)\n",
    "            else:\n",
    "                break\n",
    "        # print(dp)\n",
    "        ret = 0\n",
    "        \n",
    "        cnt = 0\n",
    "        while True:\n",
    "            cnt += 1\n",
    "            if cnt > k:\n",
    "                break\n",
    "            cur = 0\n",
    "            for i in range(len(dp)):\n",
    "                if dp[i] > 0:\n",
    "                    dp[i] -= 1\n",
    "                    cur += pow(2,i)\n",
    "            if cur == 0:\n",
    "                break\n",
    "            # print('num:',cur,'dp:',dp)\n",
    "            ret += (cur ** 2) % MOD\n",
    "        # print('')\n",
    "        return ret % MOD\n",
    "                    \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        n=max(nums).bit_length()\n",
    "        cnt=[0]*n\n",
    "        for x in nums:\n",
    "            for i in range(n):\n",
    "                cnt[i]+=x>>i&1\n",
    "        res=0\n",
    "        for i in range(k):\n",
    "            t=0\n",
    "            for j in range(n):\n",
    "                if cnt[j]!=0:\n",
    "                    t+=2**j\n",
    "                    cnt[j]-=1\n",
    "            res+=t**2\n",
    "        return res%(10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        bit_count = [0] * 32\n",
    "        for v in nums:\n",
    "            for j in range(32):\n",
    "                bit_count[j] += ((v >> j) & 1)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            v = 0\n",
    "            for j in range(32):\n",
    "                if bit_count[j]:\n",
    "                    bit_count[j] -= 1\n",
    "                    v += (1 << j)\n",
    "            ans = (ans + v * v) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        MOD = (int(1e9) + 7)\n",
    "\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        for x in nums:\n",
    "            i = 0\n",
    "            while x != 0:\n",
    "                if x & 1 == 1:\n",
    "                    d[i] += 1\n",
    "                x = x >> 1\n",
    "                i += 1\n",
    "\n",
    "        ones = sorted(list(d.keys()), reverse=True)\n",
    "\n",
    "        buf = []\n",
    "        for i in range(k):\n",
    "            x = 0\n",
    "            for i in ones:\n",
    "                if d[i] > 0:\n",
    "                    x = x | (1 << i)\n",
    "                    d[i] -= 1\n",
    "\n",
    "            buf.append(x)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        for x in buf:\n",
    "            ret += (x ** 2) % MOD\n",
    "\n",
    "        return ret % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, nums: List[int], k: int) -> int:\n",
    "        m = max(nums).bit_length()\n",
    "        cnt = [0] * m\n",
    "        for x in nums:\n",
    "            for i in range(m):\n",
    "                cnt[i] += x>>i & 1\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            x = 0\n",
    "            for i in range(m):\n",
    "                if cnt[i]:\n",
    "                    cnt[i] -=1\n",
    "                    x |= 1<<i\n",
    "            ans +=x*x\n",
    "        return ans%(10**9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
